﻿Imports Runa.Foundation.Collections

Namespace Global.Runa.UI.Threading

    Friend Class PriorityQueue(Of T)

        Private _cacheReusableChains As Stack(Of PriorityChain(Of T))
        Private _count As Integer
        Private _head As PriorityItem(Of T)
        Private _priorityChains As SortedList(Of Integer, PriorityChain(Of T))
        Private _tail As PriorityItem(Of T)

        Public Sub New()
            Me._priorityChains = New SortedList(Of Integer, PriorityChain(Of T))
            Me._cacheReusableChains = New Stack(Of PriorityChain(Of T))(10)
            Me._tail = Nothing
            Me._head = DirectCast(Me._tail, PriorityItem(Of T))
            Me._count = 0
        End Sub

        Public Sub ChangeItemPriority(ByVal item As PriorityItem(Of T), ByVal priority As DispatcherPriority)
            Me.RemoveItemFromPriorityChain(item)
            Dim chain As PriorityChain(Of T) = Me.GetChain(priority)
            Me.InsertItemInPriorityChain(item, chain)
        End Sub

        Public Function Dequeue() As T
            Dim count As Integer = Me._priorityChains.Count
            If count <= 0 Then
                Throw New InvalidOperationException
            End If
            Dim chain As PriorityChain(Of T) = Me._priorityChains.Values((count - 1))
            Dim head As PriorityItem(Of T) = chain.Head
            Me.RemoveItem(head)
            Return head.Data
        End Function

        Public Function Enqueue(ByVal priority As DispatcherPriority, ByVal data As T) As PriorityItem(Of T)
            Dim chain As PriorityChain(Of T) = Me.GetChain(priority)
            Dim item As New PriorityItem(Of T)(data)
            Me.InsertItemInSequentialChain(item, Me._tail)
            Me.InsertItemInPriorityChain(item, chain, chain.Tail)
            Return item
        End Function

        Private Function GetChain(ByVal priority As DispatcherPriority) As PriorityChain(Of T)
            Dim chain As PriorityChain(Of T) = Nothing
            Dim count As Integer = Me._priorityChains.Count
            If count > 0 Then
                If priority = Me._priorityChains.Keys(0) Then
                    chain = Me._priorityChains.Values(0)
                ElseIf priority = Me._priorityChains.Keys((count - 1)) Then
                    chain = Me._priorityChains.Values(count - 1)
                ElseIf ((priority > Me._priorityChains.Keys(0)) AndAlso (priority < Me._priorityChains.Keys((count - 1)))) Then
                    Me._priorityChains.TryGetValue(DirectCast(priority, Integer), chain)
                End If
            End If
            If (chain Is Nothing) Then
                If (Me._cacheReusableChains.Count > 0) Then
                    chain = Me._cacheReusableChains.Pop
                    chain.Priority = priority
                Else
                    chain = New PriorityChain(Of T)(priority)
                End If
                Me._priorityChains.Add(DirectCast(priority, Integer), chain)
            End If
            Return chain
        End Function

        Private Sub InsertItemInPriorityChain(ByVal item As PriorityItem(Of T), ByVal chain As PriorityChain(Of T))
            If (chain.Head Is Nothing) Then
                Me.InsertItemInPriorityChain(item, chain, Nothing)
            Else
                Dim after As PriorityItem(Of T) = Nothing
                after = item.SequentialPrev
                Do While (Not after Is Nothing)
                    If (after.Chain Is chain) Then
                        Exit Do
                    End If
                    after = after.SequentialPrev
                Loop
                Me.InsertItemInPriorityChain(item, chain, after)
            End If
        End Sub

        Friend Sub InsertItemInPriorityChain(ByVal item As PriorityItem(Of T), ByVal chain As PriorityChain(Of T), ByVal after As PriorityItem(Of T))
            item.Chain = chain
            If (after Is Nothing) Then
                If (Not chain.Head Is Nothing) Then
                    chain.Head.PriorityPrev = item
                    item.PriorityNext = chain.Head
                    chain.Head = item
                Else
                    chain.Tail = item
                    chain.Head = chain.Tail
                End If
            Else
                item.PriorityPrev = after
                If (Not after.PriorityNext Is Nothing) Then
                    item.PriorityNext = after.PriorityNext
                    after.PriorityNext.PriorityPrev = item
                    after.PriorityNext = item
                Else
                    after.PriorityNext = item
                    chain.Tail = item
                End If
            End If
            chain.Count += 1
        End Sub

        Friend Sub InsertItemInSequentialChain(ByVal item As PriorityItem(Of T), ByVal after As PriorityItem(Of T))
            If (after Is Nothing) Then
                If (Not Me._head Is Nothing) Then
                    Me._head.SequentialPrev = item
                    item.SequentialNext = Me._head
                    Me._head = item
                Else
                    Me._tail = item
                    Me._head = Me._tail
                End If
            Else
                item.SequentialPrev = after
                If (Not after.SequentialNext Is Nothing) Then
                    item.SequentialNext = after.SequentialNext
                    after.SequentialNext.SequentialPrev = item
                    after.SequentialNext = item
                Else
                    after.SequentialNext = item
                    Me._tail = item
                End If
            End If
            Me._count += 1
        End Sub

        Public Function Peek() As T
            Dim data As T = CType(Nothing, T)
            Dim count As Integer = Me._priorityChains.Count
            If (count > 0) Then
                Dim chain As PriorityChain(Of T) = Me._priorityChains.Values(count - 1)
                data = chain.Head.Data
            End If
            Return data
        End Function

        Public Sub RemoveItem(ByVal item As PriorityItem(Of T))
            Dim chain As PriorityChain(Of T) = item.Chain
            Me.RemoveItemFromPriorityChain(item)
            Me.RemoveItemFromSequentialChain(item)
        End Sub

        Private Sub RemoveItemFromPriorityChain(ByVal item As PriorityItem(Of T))
            If (Not item.PriorityPrev Is Nothing) Then
                item.PriorityPrev.PriorityNext = item.PriorityNext
            Else
                item.Chain.Head = item.PriorityNext
            End If
            If (Not item.PriorityNext Is Nothing) Then
                item.PriorityNext.PriorityPrev = item.PriorityPrev
            Else
                item.Chain.Tail = item.PriorityPrev
            End If
            item.PriorityNext = Nothing
            item.PriorityPrev = DirectCast(item.PriorityNext, PriorityItem(Of T))
            Dim chain As PriorityChain(Of T) = item.Chain
            chain.Count -= 1
            If (item.Chain.Count = 0) Then
                If (item.Chain.Priority = Me._priorityChains.Keys((Me._priorityChains.Count - 1))) Then
                    Me._priorityChains.RemoveAt(Me._priorityChains.Count - 1)
                Else
                    Me._priorityChains.Remove(DirectCast(item.Chain.Priority, Integer))
                End If
                If (Me._cacheReusableChains.Count < 10) Then
                    item.Chain.Priority = DispatcherPriority.Invalid
                    Me._cacheReusableChains.Push(item.Chain)
                End If
            End If
            item.Chain = Nothing
        End Sub

        Private Sub RemoveItemFromSequentialChain(ByVal item As PriorityItem(Of T))
            If (Not item.SequentialPrev Is Nothing) Then
                item.SequentialPrev.SequentialNext = item.SequentialNext
            Else
                Me._head = item.SequentialNext
            End If
            If (Not item.SequentialNext Is Nothing) Then
                item.SequentialNext.SequentialPrev = item.SequentialPrev
            Else
                Me._tail = item.SequentialPrev
            End If
            item.SequentialNext = Nothing
            item.SequentialPrev = DirectCast(item.SequentialNext, PriorityItem(Of T))
            Me._count -= 1
        End Sub

        Public ReadOnly Property MaxPriority As DispatcherPriority
            Get
                Dim count As Integer = Me._priorityChains.Count
                If (count > 0) Then
                    Return Me._priorityChains.Keys((count - 1))
                End If
                Return DispatcherPriority.Invalid
            End Get
        End Property

    End Class

End Namespace